Skip to main content

Trie

A comprehensive guide to Trie (Prefix Tree) algorithms and techniques for Data Structures and Algorithms.

Table of Contents​

  1. Introduction to Trie
  2. Basic Trie Implementation
  3. Search and Prefix Operations
  4. Advanced Trie Techniques
  5. Compressed Trie (Radix Tree)
  6. Trie with HashMap
  7. Bitwise Trie
  8. Trie Applications
  9. Usage Examples

Introduction to Trie​

A Trie (pronounced "try") is a tree-like data structure used for storing and searching strings efficiently. Also known as a prefix tree, it's particularly useful for applications involving string prefixes, autocomplete, and word games.

Key Properties​

  • Root: Empty node representing empty string
  • Edges: Represent characters
  • Nodes: Represent prefixes
  • Leaf marking: Indicates end of valid word
  • Path from root: Represents a string/prefix

Visual Representation​

        root
       /  |  \
      a   b   c
     /    |    \
    p     a     a
   /      |      \
  p       t       t
 /        |       |
e         h       h
(ape)   (bath)   (cat)

When to Use Trie​

  • Prefix-based searches (autocomplete, search suggestions)
  • Word games (Scrabble, Boggle, crosswords)
  • String matching with multiple patterns
  • IP routing tables
  • Dictionary operations with prefix queries
  • Longest common prefix problems

Time Complexity Overview​

OperationTimeSpace
InsertO(m)O(ALPHABET_SIZE × N × M)
SearchO(m)-
DeleteO(m)-
Prefix SearchO(p)-

Where m = length of word, p = length of prefix, N = number of words, M = average length

Basic Trie Implementation​

1. Array-based Trie Node​

class TrieNode {
    constructor() {
        this.children = new Array(26).fill(null); // For lowercase a-z
        this.isEndOfWord = false;
        this.count = 0; // Optional: count of words ending here
    }
}

class Trie {
    constructor() {
        this.root = new TrieNode();
    }

    // Helper function to get character index
    getIndex(char) {
        return char.charCodeAt(0) - 'a'.charCodeAt(0);
    }

    // Insert a word into the trie
    insert(word) {
        let current = this.root;

        for (const char of word) {
            const index = this.getIndex(char);

            if (current.children[index] === null) {
                current.children[index] = new TrieNode();
            }

            current = current.children[index];
        }

        current.isEndOfWord = true;
        current.count++;
    }

    // Search for a word in the trie
    search(word) {
        let current = this.root;

        for (const char of word) {
            const index = this.getIndex(char);

            if (current.children[index] === null) {
                return false;
            }

            current = current.children[index];
        }

        return current.isEndOfWord;
    }

    // Check if any word starts with the given prefix
    startsWith(prefix) {
        let current = this.root;

        for (const char of prefix) {
            const index = this.getIndex(char);

            if (current.children[index] === null) {
                return false;
            }

            current = current.children[index];
        }

        return true;
    }
}

Time Complexity: O(m) for all operations | Space Complexity: O(ALPHABET_SIZE × N × M)

2. HashMap-based Trie Node (More Flexible)​

class TrieNodeMap {
    constructor() {
        this.children = new Map();
        this.isEndOfWord = false;
        this.count = 0;
    }
}

class TrieMap {
    constructor() {
        this.root = new TrieNodeMap();
    }

    insert(word) {
        let current = this.root;

        for (const char of word) {
            if (!current.children.has(char)) {
                current.children.set(char, new TrieNodeMap());
            }
            current = current.children.get(char);
        }

        current.isEndOfWord = true;
        current.count++;
    }

    search(word) {
        let current = this.root;

        for (const char of word) {
            if (!current.children.has(char)) {
                return false;
            }
            current = current.children.get(char);
        }

        return current.isEndOfWord;
    }

    startsWith(prefix) {
        let current = this.root;

        for (const char of prefix) {
            if (!current.children.has(char)) {
                return false;
            }
            current = current.children.get(char);
        }

        return true;
    }

    // Get all words with given prefix
    getWordsWithPrefix(prefix) {
        let current = this.root;

        // Navigate to prefix node
        for (const char of prefix) {
            if (!current.children.has(char)) {
                return [];
            }
            current = current.children.get(char);
        }

        // DFS to collect all words
        const words = [];
        this.dfs(current, prefix, words);
        return words;
    }

    dfs(node, currentWord, words) {
        if (node.isEndOfWord) {
            words.push(currentWord);
        }

        for (const [char, childNode] of node.children) {
            this.dfs(childNode, currentWord + char, words);
        }
    }
}

🔧 Technique: HashMap-based implementation handles any character set (Unicode, special chars)!

Search and Prefix Operations​

1. Word Search with Wildcards​

class WildcardTrie extends TrieMap {
    // Search with '.' as wildcard matching any character
    searchWildcard(word) {
        return this.searchHelper(this.root, word, 0);
    }

    searchHelper(node, word, index) {
        if (index === word.length) {
            return node.isEndOfWord;
        }

        const char = word[index];

        if (char === '.') {
            // Try all possible characters
            for (const childNode of node.children.values()) {
                if (this.searchHelper(childNode, word, index + 1)) {
                    return true;
                }
            }
            return false;
        } else {
            // Regular character
            if (!node.children.has(char)) {
                return false;
            }
            return this.searchHelper(node.children.get(char), word, index + 1);
        }
    }
}

2. Auto-complete System​

class AutoComplete {
    constructor() {
        this.trie = new TrieMap();
        this.frequencies = new Map();
    }

    // Add sentence with frequency
    input(sentence, frequency = 1) {
        this.frequencies.set(sentence, (this.frequencies.get(sentence) || 0) + frequency);
        this.trie.insert(sentence);
    }

    // Get top k suggestions for prefix
    search(prefix, k = 3) {
        const words = this.trie.getWordsWithPrefix(prefix);

        // Sort by frequency (descending) then lexicographically
        words.sort((a, b) => {
            const freqA = this.frequencies.get(a) || 0;
            const freqB = this.frequencies.get(b) || 0;

            if (freqA !== freqB) {
                return freqB - freqA;
            }
            return a.localeCompare(b);
        });

        return words.slice(0, k);
    }
}

3. Word Break with Trie​

function wordBreakTrie(s, wordDict) {
    // Build trie from dictionary
    const trie = new TrieMap();
    for (const word of wordDict) {
        trie.insert(word);
    }

    const memo = new Map();

    function canBreak(start) {
        if (start === s.length) return true;
        if (memo.has(start)) return memo.get(start);

        let current = trie.root;

        for (let i = start; i < s.length; i++) {
            const char = s[i];

            if (!current.children.has(char)) {
                break;
            }

            current = current.children.get(char);

            if (current.isEndOfWord && canBreak(i + 1)) {
                memo.set(start, true);
                return true;
            }
        }

        memo.set(start, false);
        return false;
    }

    return canBreak(0);
}

4. Longest Word in Dictionary​

function longestWord(words) {
    const trie = new TrieMap();

    // Insert all words
    for (const word of words) {
        trie.insert(word);
    }

    let longestWord = "";

    function dfs(node, currentWord) {
        // Update longest word if current is longer (or lexicographically smaller)
        if (currentWord.length > longestWord.length ||
            (currentWord.length === longestWord.length && currentWord < longestWord)) {
            longestWord = currentWord;
        }

        for (const [char, childNode] of node.children) {
            // Only continue if the prefix is also a valid word
            if (childNode.isEndOfWord) {
                dfs(childNode, currentWord + char);
            }
        }
    }

    dfs(trie.root, "");
    return longestWord;
}

Advanced Trie Techniques​

1. Delete Operation with Cleanup​

class AdvancedTrie extends TrieMap {
    delete(word) {
        return this.deleteHelper(this.root, word, 0);
    }

    deleteHelper(node, word, index) {
        if (index === word.length) {
            // Reached end of word
            if (!node.isEndOfWord) {
                return false; // Word doesn't exist
            }

            node.isEndOfWord = false;
            node.count = 0;

            // Return true if node has no children (can be deleted)
            return node.children.size === 0;
        }

        const char = word[index];
        const childNode = node.children.get(char);

        if (!childNode) {
            return false; // Word doesn't exist
        }

        const shouldDeleteChild = this.deleteHelper(childNode, word, index + 1);

        if (shouldDeleteChild) {
            node.children.delete(char);

            // Return true if current node can also be deleted
            return !node.isEndOfWord && node.children.size === 0;
        }

        return false;
    }

    // Check if trie is empty
    isEmpty() {
        return this.root.children.size === 0;
    }

    // Get total number of words
    getTotalWords() {
        return this.getTotalWordsHelper(this.root);
    }

    getTotalWordsHelper(node) {
        let count = node.count;

        for (const childNode of node.children.values()) {
            count += this.getTotalWordsHelper(childNode);
        }

        return count;
    }
}

2. Longest Common Prefix​

function longestCommonPrefix(words) {
    if (!words || words.length === 0) return "";

    const trie = new TrieMap();

    // Insert all words
    for (const word of words) {
        trie.insert(word);
    }

    let lcp = "";
    let current = trie.root;

    // Traverse while there's exactly one child and no word ends here
    while (current.children.size === 1 && !current.isEndOfWord) {
        const char = current.children.keys().next().value;
        lcp += char;
        current = current.children.get(char);
    }

    return lcp;
}

3. Count Distinct Substrings​

function countDistinctSubstrings(s) {
    const trie = new TrieMap();

    // Insert all suffixes
    for (let i = 0; i < s.length; i++) {
        let current = trie.root;

        for (let j = i; j < s.length; j++) {
            const char = s[j];

            if (!current.children.has(char)) {
                current.children.set(char, new TrieNodeMap());
            }

            current = current.children.get(char);
        }
    }

    // Count nodes (excluding root)
    return countNodes(trie.root) - 1;
}

function countNodes(node) {
    let count = 1; // Count current node

    for (const childNode of node.children.values()) {
        count += countNodes(childNode);
    }

    return count;
}

4. Replace Words (Root Dictionary)​

function replaceWords(dictionary, sentence) {
    const trie = new TrieMap();

    // Build trie with dictionary roots
    for (const root of dictionary) {
        trie.insert(root);
    }

    const words = sentence.split(' ');
    const result = [];

    for (const word of words) {
        let current = trie.root;
        let replacement = "";
        let found = false;

        for (const char of word) {
            if (!current.children.has(char)) {
                break;
            }

            replacement += char;
            current = current.children.get(char);

            if (current.isEndOfWord) {
                found = true;
                break;
            }
        }

        result.push(found ? replacement : word);
    }

    return result.join(' ');
}

Compressed Trie (Radix Tree)​

Space-optimized trie that compresses chains of single-child nodes.

1. Radix Tree Implementation​

class RadixNode {
    constructor(label = "") {
        this.label = label; // String label for this edge
        this.children = new Map();
        this.isEndOfWord = false;
    }
}

class RadixTree {
    constructor() {
        this.root = new RadixNode();
    }

    insert(word) {
        this.insertHelper(this.root, word);
    }

    insertHelper(node, word) {
        if (word.length === 0) {
            node.isEndOfWord = true;
            return;
        }

        const firstChar = word[0];

        if (node.children.has(firstChar)) {
            const child = node.children.get(firstChar);
            const commonLength = this.getCommonPrefixLength(child.label, word);

            if (commonLength === child.label.length) {
                // Full match with child label, continue recursively
                this.insertHelper(child, word.substring(commonLength));
            } else {
                // Partial match, need to split the node
                this.splitNode(child, commonLength);
                this.insertHelper(child, word.substring(commonLength));
            }
        } else {
            // No matching child, create new node
            const newNode = new RadixNode(word);
            newNode.isEndOfWord = true;
            node.children.set(firstChar, newNode);
        }
    }

    getCommonPrefixLength(str1, str2) {
        let i = 0;
        while (i < str1.length && i < str2.length && str1[i] === str2[i]) {
            i++;
        }
        return i;
    }

    splitNode(node, splitIndex) {
        const remainingLabel = node.label.substring(splitIndex);
        const originalChildren = new Map(node.children);
        const originalIsEndOfWord = node.isEndOfWord;

        // Create new child with remaining label
        const newChild = new RadixNode(remainingLabel);
        newChild.children = originalChildren;
        newChild.isEndOfWord = originalIsEndOfWord;

        // Update current node
        node.label = node.label.substring(0, splitIndex);
        node.children.clear();
        node.children.set(remainingLabel[0], newChild);
        node.isEndOfWord = false;
    }

    search(word) {
        let current = this.root;
        let remaining = word;

        while (remaining.length > 0) {
            const firstChar = remaining[0];

            if (!current.children.has(firstChar)) {
                return false;
            }

            const child = current.children.get(firstChar);

            if (remaining.startsWith(child.label)) {
                remaining = remaining.substring(child.label.length);
                current = child;
            } else {
                return false;
            }
        }

        return current.isEndOfWord;
    }
}

⚡ Optimization: Radix trees use O(n) space in worst case vs O(ALPHABET_SIZE × n) for regular tries!

Trie with HashMap​

Advanced applications using tries with additional data structures.

1. Word Search II (Board + Dictionary)​

function findWords(board, words) {
    // Build trie from words
    const trie = new TrieMap();
    for (const word of words) {
        trie.insert(word);
    }

    const result = new Set();
    const rows = board.length;
    const cols = board[0].length;
    const directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];

    function dfs(row, col, node, currentWord, visited) {
        if (row < 0 || row >= rows || col < 0 || col >= cols) return;
        if (visited.has(`${row},${col}`)) return;

        const char = board[row][col];
        if (!node.children.has(char)) return;

        const childNode = node.children.get(char);
        const newWord = currentWord + char;

        if (childNode.isEndOfWord) {
            result.add(newWord);
        }

        visited.add(`${row},${col}`);

        for (const [dr, dc] of directions) {
            dfs(row + dr, col + dc, childNode, newWord, visited);
        }

        visited.delete(`${row},${col}`);
    }

    // Start DFS from each cell
    for (let i = 0; i < rows; i++) {
        for (let j = 0; j < cols; j++) {
            dfs(i, j, trie.root, "", new Set());
        }
    }

    return Array.from(result);
}

2. Top K Frequent Words​

function topKFrequent(words, k) {
    // Count frequencies
    const frequency = new Map();
    for (const word of words) {
        frequency.set(word, (frequency.get(word) || 0) + 1);
    }

    // Build trie with frequency information
    class FreqTrieNode extends TrieNodeMap {
        constructor() {
            super();
            this.frequency = 0;
        }
    }

    const trie = new TrieMap();
    trie.root = new FreqTrieNode();

    for (const [word, freq] of frequency) {
        let current = trie.root;

        for (const char of word) {
            if (!current.children.has(char)) {
                current.children.set(char, new FreqTrieNode());
            }
            current = current.children.get(char);
        }

        current.isEndOfWord = true;
        current.frequency = freq;
    }

    // Collect words with frequencies
    const wordsWithFreq = [];

    function collectWords(node, currentWord) {
        if (node.isEndOfWord) {
            wordsWithFreq.push([currentWord, node.frequency]);
        }

        for (const [char, childNode] of node.children) {
            collectWords(childNode, currentWord + char);
        }
    }

    collectWords(trie.root, "");

    // Sort by frequency (desc) then lexicographically (asc)
    wordsWithFreq.sort(([wordA, freqA], [wordB, freqB]) => {
        if (freqA !== freqB) return freqB - freqA;
        return wordA.localeCompare(wordB);
    });

    return wordsWithFreq.slice(0, k).map(([word, freq]) => word);
}

3. Stream of Characters​

class StreamChecker {
    constructor(words) {
        this.trie = new TrieMap();
        this.stream = "";
        this.maxWordLength = 0;

        // Insert reversed words for suffix matching
        for (const word of words) {
            const reversedWord = word.split('').reverse().join('');
            this.trie.insert(reversedWord);
            this.maxWordLength = Math.max(this.maxWordLength, word.length);
        }
    }

    query(letter) {
        this.stream += letter;

        // Keep only last maxWordLength characters
        if (this.stream.length > this.maxWordLength) {
            this.stream = this.stream.substring(this.stream.length - this.maxWordLength);
        }

        // Check if any suffix of reversed stream matches a word
        let current = this.trie.root;

        for (let i = this.stream.length - 1; i >= 0; i--) {
            const char = this.stream[i];

            if (!current.children.has(char)) {
                return false;
            }

            current = current.children.get(char);

            if (current.isEndOfWord) {
                return true;
            }
        }

        return false;
    }
}

Bitwise Trie​

Special trie for handling binary representations and XOR operations.

1. Maximum XOR Trie​

class BitTrieNode {
    constructor() {
        this.children = new Array(2).fill(null); // 0 and 1
        this.value = -1; // Store the actual number at leaf
    }
}

class BitTrie {
    constructor() {
        this.root = new BitTrieNode();
    }

    insert(num) {
        let current = this.root;

        // Process 32 bits from MSB to LSB
        for (let i = 31; i >= 0; i--) {
            const bit = (num >> i) & 1;

            if (current.children[bit] === null) {
                current.children[bit] = new BitTrieNode();
            }

            current = current.children[bit];
        }

        current.value = num;
    }

    findMaxXOR(num) {
        let current = this.root;
        let maxXOR = 0;

        for (let i = 31; i >= 0; i--) {
            const bit = (num >> i) & 1;
            const oppositeBit = 1 - bit;

            if (current.children[oppositeBit] !== null) {
                maxXOR |= (1 << i);
                current = current.children[oppositeBit];
            } else {
                current = current.children[bit];
            }
        }

        return maxXOR;
    }
}

function findMaximumXOR(nums) {
    const trie = new BitTrie();
    let maxXOR = 0;

    // Insert first number
    trie.insert(nums[0]);

    // For each subsequent number, find max XOR and insert it
    for (let i = 1; i < nums.length; i++) {
        maxXOR = Math.max(maxXOR, trie.findMaxXOR(nums[i]));
        trie.insert(nums[i]);
    }

    return maxXOR;
}

2. Count Pairs with XOR in Range​

function countPairsInRange(nums, low, high) {
    const trie = new BitTrie();

    function countPairsWithMaxXOR(maxXOR) {
        let count = 0;

        for (const num of nums) {
            count += countPairsHelper(trie.root, num, maxXOR, 31);
            trie.insert(num);
        }

        return count;
    }

    function countPairsHelper(node, num, maxXOR, bit) {
        if (bit < 0) return 1;

        const numBit = (num >> bit) & 1;
        const maxBit = (maxXOR >> bit) & 1;
        let count = 0;

        if (maxBit === 1) {
            // Can take either path
            if (node.children[numBit] !== null) {
                count += countPairsHelper(node.children[numBit], num, maxXOR, bit - 1);
            }
            if (node.children[1 - numBit] !== null) {
                count += countPairsHelper(node.children[1 - numBit], num, maxXOR, bit - 1);
            }
        } else {
            // Must take the same bit to stay <= maxXOR
            const requiredBit = numBit;
            if (node.children[requiredBit] !== null) {
                count += countPairsHelper(node.children[requiredBit], num, maxXOR, bit - 1);
            }
        }

        return count;
    }

    return countPairsWithMaxXOR(high) - countPairsWithMaxXOR(low - 1);
}

Trie Applications​

1. Phone Directory (T9 Predictive Text)​

class T9Trie {
    constructor() {
        // Map phone digits to letters
        this.digitToLetters = {
            '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
            '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'
        };

        this.letterToDigit = {};

        // Build reverse mapping
        for (const [digit, letters] of Object.entries(this.digitToLetters)) {
            for (const letter of letters) {
                this.letterToDigit[letter] = digit;
            }
        }

        this.trie = new TrieMap();
    }

    addWord(word) {
        // Convert word to digit sequence
        const digitSequence = word.toLowerCase()
            .split('')
            .map(char => this.letterToDigit[char] || char)
            .join('');

        // Store both digit sequence and original word
        let current = this.trie.root;

        for (const digit of digitSequence) {
            if (!current.children.has(digit)) {
                current.children.set(digit, new TrieNodeMap());
                current.children.get(digit).words = [];
            }
            current = current.children.get(digit);
        }

        if (!current.words) current.words = [];
        current.words.push(word);
        current.isEndOfWord = true;
    }

    getSuggestions(digitSequence, maxSuggestions = 10) {
        let current = this.trie.root;

        // Navigate to the digit sequence
        for (const digit of digitSequence) {
            if (!current.children.has(digit)) {
                return [];
            }
            current = current.children.get(digit);
        }

        // Collect all words from this point
        const suggestions = [];
        this.collectWords(current, suggestions);

        return suggestions.slice(0, maxSuggestions);
    }

    collectWords(node, result) {
        if (node.words) {
            result.push(...node.words);
        }

        for (const childNode of node.children.values()) {
            this.collectWords(childNode, result);
        }
    }
}

2. Spell Checker with Edit Distance​

class SpellChecker {
    constructor(dictionary) {
        this.trie = new TrieMap();

        for (const word of dictionary) {
            this.trie.insert(word.toLowerCase());
        }
    }

    // Find words within edit distance k
    findSimilarWords(word, maxDistance = 1) {
        const results = [];
        const wordLower = word.toLowerCase();

        this.searchWithDistance(this.trie.root, "", wordLower, maxDistance, results);

        return results;
    }

    searchWithDistance(node, currentWord, targetWord, remainingDistance, results) {
        // If we've matched the entire target word
        if (targetWord.length === 0) {
            if (node.isEndOfWord) {
                results.push(currentWord);
            }
            // Continue to find longer words if we have remaining distance
            if (remainingDistance > 0) {
                for (const [char, childNode] of node.children) {
                    this.searchWithDistance(childNode, currentWord + char, "", remainingDistance - 1, results);
                }
            }
            return;
        }

        const targetChar = targetWord[0];
        const remainingTarget = targetWord.substring(1);

        for (const [char, childNode] of node.children) {
            if (char === targetChar) {
                // Exact match - no cost
                this.searchWithDistance(childNode, currentWord + char, remainingTarget, remainingDistance, results);
            } else if (remainingDistance > 0) {
                // Substitution - cost 1
                this.searchWithDistance(childNode, currentWord + char, remainingTarget, remainingDistance - 1, results);
            }
        }

        // Insertion - add character from target without moving in trie
        if (remainingDistance > 0) {
            this.searchWithDistance(node, currentWord + targetChar, remainingTarget, remainingDistance - 1, results);
        }

        // Deletion - move in trie without consuming target character
        if (remainingDistance > 0) {
            for (const [char, childNode] of node.children) {
                this.searchWithDistance(childNode, currentWord + char, targetWord, remainingDistance - 1, results);
            }
        }
    }

    // Simple spell check with suggestions
    spellCheck(word) {
        const wordLower = word.toLowerCase();

        if (this.trie.search(wordLower)) {
            return { isCorrect: true, suggestions: [] };
        }

        const suggestions = this.findSimilarWords(wordLower, 2);
        return { isCorrect: false, suggestions };
    }
}

3. IP Address Trie (Longest Prefix Match)​

class IPTrie {
    constructor() {
        this.root = new TrieNodeMap();
        this.root.route = null; // Store routing information
    }

    // Convert IP to binary string
    ipToBinary(ip) {
        return ip.split('.').map(octet => {
            return parseInt(octet).toString(2).padStart(8, '0');
        }).join('');
    }

    // Add route with CIDR notation (e.g., "192.168.1.0/24")
    addRoute(cidr, routeInfo) {
        const [ip, prefixLength] = cidr.split('/');
        const binaryIP = this.ipToBinary(ip);
        const prefix = binaryIP.substring(0, parseInt(prefixLength));

        let current = this.root;

        for (const bit of prefix) {
            if (!current.children.has(bit)) {
                current.children.set(bit, new TrieNodeMap());
                current.children.get(bit).route = null;
            }
            current = current.children.get(bit);
        }

        current.route = routeInfo;
    }

    // Find longest prefix match for an IP
    longestPrefixMatch(ip) {
        const binaryIP = this.ipToBinary(ip);
        let current = this.root;
        let lastMatchedRoute = current.route;

        for (const bit of binaryIP) {
            if (!current.children.has(bit)) {
                break;
            }

            current = current.children.get(bit);

            if (current.route !== null) {
                lastMatchedRoute = current.route;
            }
        }

        return lastMatchedRoute;
    }
}

// Usage example
const ipTrie = new IPTrie();
ipTrie.addRoute("192.168.1.0/24", { gateway: "192.168.1.1", interface: "eth0" });
ipTrie.addRoute("192.168.0.0/16", { gateway: "192.168.0.1", interface: "eth1" });
ipTrie.addRoute("0.0.0.0/0", { gateway: "10.0.0.1", interface: "eth2" }); // Default route

console.log(ipTrie.longestPrefixMatch("192.168.1.100")); // Should match /24 route

4. Boggle Game Solver​

function findWordsInBoggle(board, dictionary) {
    // Build trie from dictionary
    const trie = new TrieMap();
    for (const word of dictionary) {
        trie.insert(word.toUpperCase());
    }

    const rows = board.length;
    const cols = board[0].length;
    const directions = [
        [-1, -1], [-1, 0], [-1, 1],
        [0, -1],           [0, 1],
        [1, -1],  [1, 0],  [1, 1]
    ];

    const foundWords = new Set();

    function dfs(row, col, node, currentWord, visited) {
        if (row < 0 || row >= rows || col < 0 || col >= cols) return;
        if (visited[row][col]) return;

        const char = board[row][col].toUpperCase();
        if (!node.children.has(char)) return;

        const childNode = node.children.get(char);
        const newWord = currentWord + char;

        // Mark as visited
        visited[row][col] = true;

        // If we found a complete word (and it's at least 3 characters long)
        if (childNode.isEndOfWord && newWord.length >= 3) {
            foundWords.add(newWord);
        }

        // Continue searching in all directions
        for (const [dr, dc] of directions) {
            dfs(row + dr, col + dc, childNode, newWord, visited);
        }

        // Backtrack
        visited[row][col] = false;
    }

    // Start DFS from each cell
    for (let i = 0; i < rows; i++) {
        for (let j = 0; j < cols; j++) {
            const visited = Array(rows).fill(null).map(() => Array(cols).fill(false));
            dfs(i, j, trie.root, "", visited);
        }
    }

    return Array.from(foundWords).sort();
}

Usage Examples​

console.log("=== Trie Data Structure Demo ===");

// Basic Trie Operations
const trie = new TrieMap();
const words = ["apple", "app", "application", "apply", "banana"];

for (const word of words) {
    trie.insert(word);
}

console.log("Search 'app':", trie.search("app")); // true
console.log("Search 'appl':", trie.search("appl")); // false
console.log("Starts with 'app':", trie.startsWith("app")); // true
console.log("Words with prefix 'app':", trie.getWordsWithPrefix("app"));
// ["app", "apple", "application", "apply"]

// Wildcard Search
const wildcardTrie = new WildcardTrie();
wildcardTrie.insert("bad");
wildcardTrie.insert("dad");
wildcardTrie.insert("mad");

console.log("Search 'b.d':", wildcardTrie.searchWildcard("b.d")); // true
console.log("Search '.ad':", wildcardTrie.searchWildcard(".ad")); // true

// Auto-complete System
const autoComplete = new AutoComplete();
autoComplete.input("i love you", 5);
autoComplete.input("island", 3);
autoComplete.input("i love leetcode", 2);

console.log("Autocomplete 'i':", autoComplete.search("i", 3));
// ["i love you", "island", "i love leetcode"]

// Word Break
const wordDict = ["apple", "pen", "applepen", "pine", "pineapple"];
console.log("Word break 'pineapplepenapple':",
    wordBreakTrie("pineapplepenapple", wordDict)); // true

// Longest Common Prefix
const words2 = ["flower", "flow", "flight"];
console.log("Longest common prefix:", longestCommonPrefix(words2)); // "fl"

// Replace Words
const dictionary = ["cat", "bat", "rat"];
const sentence = "the cattle was rattled by the battery";
console.log("Replace words:", replaceWords(dictionary, sentence));
// "the cat was rat by the bat"

// Maximum XOR
const nums = [3, 10, 5, 25, 2, 8];
console.log("Maximum XOR:", findMaximumXOR(nums)); // 28

// Spell Checker
const spellChecker = new SpellChecker(["hello", "world", "help", "held"]);
console.log("Spell check 'helo':", spellChecker.spellCheck("helo"));
// { isCorrect: false, suggestions: ["hello", "help", "held"] }

// Boggle Solver
const board = [
    ['E', 'A', 'A', 'N'],
    ['T', 'T', 'A', 'E'],
    ['I', 'H', 'K', 'R'],
    ['I', 'F', 'L', 'V']
];
const boggleDict = ["eat", "rain", "hike", "fire", "lair"];
console.log("Boggle words:", findWordsInBoggle(board, boggleDict));

// IP Routing
const ipTrie = new IPTrie();
ipTrie.addRoute("192.168.1.0/24", { gateway: "192.168.1.1" });
ipTrie.addRoute("0.0.0.0/0", { gateway: "10.0.0.1" });

console.log("Route for 192.168.1.100:", ipTrie.longestPrefixMatch("192.168.1.100"));

Time Complexity Summary​

OperationTrieCompressed TrieHash Map
InsertO(m)O(m)O(1) avg
SearchO(m)O(m)O(1) avg
DeleteO(m)O(m)O(1) avg
Prefix SearchO(p)O(p)O(n)
SpaceO(ALPHABET × N × M)O(N × M)O(N × M)

Where m = word length, p = prefix length, N = number of words, M = average word length

Common Patterns to Remember​

1. Basic Trie Template​

class TrieNode {
    constructor() {
        this.children = new Map(); // or Array for fixed alphabet
        this.isEndOfWord = false;
    }
}

class Trie {
    constructor() {
        this.root = new TrieNode();
    }

    insert(word) {
        let current = this.root;
        for (const char of word) {
            if (!current.children.has(char)) {
                current.children.set(char, new TrieNode());
            }
            current = current.children.get(char);
        }
        current.isEndOfWord = true;
    }
}

2. DFS for Word Collection​

function collectWords(node, prefix, result) {
    if (node.isEndOfWord) {
        result.push(prefix);
    }

    for (const [char, childNode] of node.children) {
        collectWords(childNode, prefix + char, result);
    }
}

3. Backtracking with Trie​

function dfsWithBacktrack(board, row, col, node, currentWord, visited, result) {
    // Boundary checks
    if (row < 0 || row >= rows || col < 0 || col >= cols) return;
    if (visited[row][col]) return;

    const char = board[row][col];
    if (!node.children.has(char)) return;

    // Mark visited
    visited[row][col] = true;
    const childNode = node.children.get(char);

    if (childNode.isEndOfWord) {
        result.add(currentWord + char);
    }

    // Explore neighbors
    for (const [dr, dc] of directions) {
        dfsWithBacktrack(board, row + dr, col + dc, childNode, currentWord + char, visited, result);
    }

    // Backtrack
    visited[row][col] = false;
}

4. Bitwise Trie for XOR​

class BitTrie {
    insert(num) {
        let current = this.root;
        for (let i = 31; i >= 0; i--) {
            const bit = (num >> i) & 1;
            if (!current.children[bit]) {
                current.children[bit] = new BitTrieNode();
            }
            current = current.children[bit];
        }
    }

    findMaxXOR(num) {
        let current = this.root;
        let maxXOR = 0;

        for (let i = 31; i >= 0; i--) {
            const bit = (num >> i) & 1;
            const oppositeBit = 1 - bit;

            if (current.children[oppositeBit]) {
                maxXOR |= (1 << i);
                current = current.children[oppositeBit];
            } else {
                current = current.children[bit];
            }
        }

        return maxXOR;
    }
}

5. Delete with Cleanup​

function deleteWord(node, word, index) {
    if (index === word.length) {
        if (!node.isEndOfWord) return false;
        node.isEndOfWord = false;
        return node.children.size === 0; // Can delete if no children
    }

    const char = word[index];
    const childNode = node.children.get(char);

    if (!childNode) return false;

    const shouldDelete = deleteWord(childNode, word, index + 1);

    if (shouldDelete) {
        node.children.delete(char);
        return !node.isEndOfWord && node.children.size === 0;
    }

    return false;
}

Key Interview Tips​

Problem Recognition Checklist​

Use Trie when you see:

  • ✅ Prefix-based operations (autocomplete, search suggestions)
  • ✅ Word games (Boggle, Scrabble, crosswords)
  • ✅ Multiple pattern matching in strings
  • ✅ Dictionary operations with prefix queries
  • ✅ String collections with common prefixes
  • ✅ Longest common prefix problems

Use Bitwise Trie for:

  • ✅ XOR problems with arrays of numbers
  • ✅ Maximum/minimum XOR queries
  • ✅ Bit manipulation on collections

Common Mistakes to Avoid​

  1. Forgetting isEndOfWord: Not marking word endings properly
  2. Memory leaks: Not cleaning up nodes during deletion
  3. Case sensitivity: Inconsistent handling of upper/lowercase
  4. Null pointer errors: Not checking if children exist
  5. Over-engineering: Using trie when hash map would suffice

Space vs Time Tradeoffs​

ScenarioTrie AdvantageHash Map Advantage
Prefix operationsO(p) prefix searchO(n) to find all prefixes
Memory usageShared prefixes save spaceEach word stored separately
Insertion/SearchO(m) guaranteedO(1) average case
ImplementationMore complexSimpler

Performance Optimization Tips​

  1. Use arrays for fixed alphabets (26 lowercase letters)
  2. Use hash maps for arbitrary characters (Unicode, mixed case)
  3. Consider compressed tries for sparse data
  4. Add early termination in search algorithms
  5. Implement lazy deletion for better performance

Advanced Techniques​

Trie with Suffix Arrays​

// For advanced string algorithms
class SuffixTrie {
    constructor(text) {
        this.trie = new TrieMap();
        this.buildSuffixTrie(text);
    }

    buildSuffixTrie(text) {
        for (let i = 0; i < text.length; i++) {
            this.trie.insert(text.substring(i));
        }
    }
}

Concurrent Trie (Thread-Safe)​

class ConcurrentTrie {
    constructor() {
        this.trie = new TrieMap();
        this.locks = new Map(); // Simplified locking mechanism
    }

    // Add proper synchronization for multi-threaded environments
    safeInsert(word) {
        // Implementation would include proper locking
        this.trie.insert(word);
    }
}

This comprehensive guide covers all essential Trie techniques for coding interviews and competitive programming. The combination of trie with various algorithms (DFS, backtracking, bit manipulation) makes it a versatile data structure for many string and prefix-related problems!

Practice Problems by Difficulty​

Beginner​

  1. Implement Trie (Prefix Tree)
  2. Longest Common Prefix
  3. Design Add and Search Words Data Structure

Intermediate​

  1. Word Search II
  2. Replace Words
  3. Top K Frequent Words
  4. Stream of Characters
  5. Word Break with Trie

Advanced​

  1. Maximum XOR of Two Numbers in Array
  2. Count Pairs with XOR in Range
  3. Palindrome Pairs
  4. Index Pairs of a String

Expert​

  1. Design Search Autocomplete System
  2. Word Squares
  3. Concatenated Words
  4. Number of Distinct Substrings using Suffix Trie